#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool vis[26] = { false };
    bool letter[26][26] = { false };
    int mmin[26];
    void dfs(int start, int k)
    {
        if (vis[k])
            return;
        vis[k] = true;
        mmin[k] = start;
        for (int i = 0; i < 26; i++)
        {
            if (letter[k][i] && !vis[i])
            {
                dfs(start, i);
            }
        }
    }
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        int n = s1.size();
        for (auto& e : mmin) e = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            int a = s1[i] - 'a', b = s2[i] - 'a';
            letter[a][b] = true, letter[b][a] = true;;
        }
        for (int i = 0; i < 26; i++) dfs(i, i);

        for (auto& c : baseStr) c = mmin[c - 'a'] + 'a';
        return baseStr;
    }
};